package com.jerry.hm.algorithm.recursion;

/**
 * 插入排序
 *
 * @author Jerry
 * @since 2024/9/30 19:59
 */
public class InsertionSort {

    public static void sort(int[] arr) {
        insertion(arr, 1);
    }

    /**
     * 插入排序
     *
     * @param arr
     * @param left 未排序的左边界索引
     */
    private static void insertion(int[] arr, int left) {
        if (left == arr.length) {
            return;
        }

        int target = arr[left];
        int i = left - 1;

        while (i >= 0 && arr[i] > target) {
            // 比待排序数组大的都往后移
            arr[i + 1] = arr[i];
            i--;
        }

        // 插入点索引是 i + 1
        if (i + 1 != left) {
            arr[i + 1] = target;
        }

        insertion(arr, left + 1);
    }
}
